Skip to main content

Full text of "BSTJ 51: 9. November 1972: B.S.T.J. Briefs: A Table Look Up Approach to Loop Switching. (Brandenburg, L.H.; Gopinath, B.)"

See other formats


B.S.TJ. BRIEF 

A Table Look Up Approach to Loop Switching 

By L. H. BRANDENBURG and B. GOPINATH 

(Manuscript received July 24, 1972) 



In this paper we consider some questions of implementation of a 
scheme described in Section V of Ref. 1 for addressing message blocks 
in the Pierce loop system. 2 The scheme consists of using a stream of 
binary digits (0 and 1) as the address of the destination loop of a message 
such that the scalar product* of the address with a stream of binary 
digits of equal length stored at a loop gives the distance between the 
loop and the destination. The message is routed along a path that 
minimizes distance between source and destination. The binary streams 
used in this scheme can be obtained by factoring the distance matrix D 
of the graph representing the connection of loops into two binary- 
valued matrices P and Q such that 

D = PQ 1 , 

where the superscript "t" stands for matrix transposition. The fcth 
row of P represents the address to be prefixed to a message destined 
for loop k. The fcth row of Q represents a binary sequence to be stored 
in loop k. The scheme discussed in Section V of Ref. 1 provides a par- 
ticular way of factoring D. For completeness, we give a description of 
that factorization as follows. 

Let s be the diameter of a graph on n vertices and let D be its distance 
matrix. (Note: s = max,, Da). We consider a PQ 1 factorization of D 
with P and Q matrices each of order n X ns. The ith row of P, Pi , is 
zero everywhere except in positions (s(i — 1) + 1) to si where it is one. 
The ith row of Q, Q, , is constructed as follows: for every j, there are 
exactly D j{ l's in positions (s(j — 1) + 1) to sj with the rest of the 
entries of Q, equal to zero. 



* The scalar product of two binary streams of equal length is the number of places 
they both have a "one". 

2095 



2096 



P = 



THE BELL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1972 

3s m 

• • • • ■ • 6" 



s 

1 
1 



2s 

1 





1 



1 



Q = 





10 1 



1 



0_ 



D nl 



D„ 



D n 



Obviously the length of addresses in this scheme is ns. The P matrix 
defined above, rows of which are addresses to be prefixed onto messages, 
is the same for all graphs with diameter s. The Q matrix, rows of which 
are stored in the loops in the network, contains the information that 
identifies a particular graph. 

As will be discussed further, a simple mechanization of this scheme 
reveals that it is essentially an obvious table look up scheme. In a table 
look up scheme, each loop has stored the distance between it and every 
other loop in the networks, and each address essentially provides a 
signal to look up or read out a particular distance that is stored. 

The above PQ l factorization can be transformed into a table look 
up scheme in the following way. The integer i (^n) uniquely specifies 
the ith row of P; thus, a message address need only consist of the 
binary representation of i, which, of course, requires at most [log 2 ri\* 
bits. Each loop, instead of storing simply a row of matrix Q, stores 
a binary array consisting of n rows and [log 2 s] columns. The ith row 
of this array contains the binary representation of the distance between 
the loop in question and the ith loop. The binary array can be im- 
plemented by a read only memory the ith row of which is accessed by 
the binary sequence representing integer i. Note that in the original 
PQ l form of this scheme, both matrices P and Q were dependent on s, 
the diameter of the graph. In the table look up mechanization, s appears 

* [x] means "the least integer greater than x". 



LOOP SWITCHING 2097 

only in the dimension of the stored memory. (The authors had originally 
considered a table look up mechanization for minimum distance routing 
but had concentrated their early efforts on the more mathematically 
fruitful schemes discussed in Refs. 1 and 3. It is interesting to note at 
this point that the table look up mechanization has evolved in a natural 
way from a special case of one of those schemes.) 

The table look up scheme meets the following important criteria: 
(i) The simplicity of constructing addresses is important in the 
case of large graphs with no special structure. Even if one were to find 
minimum length addresses similar to the ones described in Sections I, 
II, and III of Ref. 1, we suspect that the construction of these addresses 
would be very complicated. In the present case, each address is obtained 
trivially as the binary representation of an integer. 

(ii) Since present plans for length of message blocks envisage lengths 
of perhaps a few thousand bits, the length of the message address is 
an important parameter in any large loop system. The present method 
guarantees minimum length addresses, [log 2 n], provided that the 
graph is not constrained to have a particular structure. 

(in) The scheme can be adapted by prefixing some control digits 
to do alternate routing. 

(iv) It is simple to determine the necessary changes in the stored 
memory required by updating (adding loops) or modifying the network, 
since such changes can be identified by inspection of the distance 
matrix. 

(v) The speed of operation of this scheme can be very fast compared 
to the speed of the message. 

(vi) If the graph is hierarchical in the sense of Pierce, 2 except that 
interconnections among loops at the local level are allowed, then routing 
can be accomplished by using the Pierce scheme at higher levels, and 
the present scheme at the local level. 

At first it might appear that the present scheme requires longer 
address lengths than the Pierce addressing scheme 2 for the case of 
strictly hierarchical graphs. For most cases, we show this is not so. 
A hierarchical graph of k levels can be represented as in Fig. 1. 

Ni represents the maximum of the number of branches connecting 
each vertex at the (i — l)st level, to vertices at the ith. level. Pierce's 
scheme obviously requires addresses of length ^*_, [log JV,] bits. The 
present scheme requires at most 

m = [log (1 + N t + NiNa + ■ ■ • + NrN* ■ ■ ■ N k )} bits. 



2098 THE BELL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1972 





*th LEVEL J b h H/c 

Fig. 1 — A hierarchical graph of k levels. 

But 

If, at each level, there is at least one vertex with two or more branches 
descending to the next level (this will always be the case if the levels 
"fan out") then N t £ 2 for each i. Then 

m ^ [log iV^.-.A^l +| + |*+ ••• +|f)j 

g [log 2N,N 2 ■■■N k ]^ [log N,N 2 . • . N k ] + 1. 

Therefore, if each Ni is a power of 2, then Pierce's scheme gives ad- 
dresses at most one bit shorter than those of the present scheme. How- 
ever, if even one of the N { 's is not a power of 2, then the present method 
has address lengths at most equal to those of Pierce's scheme. In fact, 
even if each N { is a power of 2, the Pierce scheme has the one bit ad- 
vantage if and only if every vertex at the ith. level has exactly N i+1 
branches connected to the (i -f- l)st level, for all levels. 

In order to compare the present scheme with other schemes described 
in Ref. 1, we assume that the important parameters are of the following 
orders: 

s = diameter of the graph tt 6 

n = number of loops tt 10 3 

length of message block ^ 4 X 10 3 bits. 



LOOP SWITCHING 2099 

Then for the present scheme, the address length ft* 10 bits, or 1/4 
percent of the message block length. The memory requirement at each 
loop is n log 2 s or ft* 3 X 10 3 bits. For these numbers, the presently 
available memories, either core or the more advanced semiconductor 
memories, could be used to realize very high speed routing of messages. 

For the other schemes in Refs. 1 and 3, the address length was con- 
jectured not to exceed 2(n — 1) bits ~ 2 X 10 3 bits, or 50 percent of 
the message block length. The memory requirement is of the same order 
or about 2/3 of that of the present scheme. 

With regard to time of computing distance at each junction, the 
table look up scheme using semiconductor memory might require 
on the order of 100 nanoseconds; on the other hand, the schemes dis- 
cussed in Refs. 1 and 3, based on inner product or Hamming distance 
calculations, might require on the order of 5,000 nanoseconds. 

These numbers, together with the six points listed previously, provide 
evidence of the practical advantage of the table look up scheme over 
the other schemes in Ref. 1. We have, of course, omitted discussion 
of such important questions as reliability and the implementation of 
updating the stored memory in each loop due to changes in the net- 
work. However, these questions are of equal importance in the present 
scheme and the schemes in Ref. 1, since the basic routing rule is the 
same (minimum distance) and the sizes of the stored memories are 
comparable as shown above. 

The authors are indebted to H. S. McDonald for helpful discussions 
concerning some of the practicalities of implementing a loop switching 
system. 

REFERENCES 

1. Brandenburg, L. H., Gopinath, B., and Kurshan, R. P., "On the Addressing 

Problem of Loop Switching," B.S.T.J., 51, No. 7 (September 1972), pp. 1445- 
1470. 

2. Pierce, J. R., "Network for Block Switching of Data," B.S.T.J., 51, No. 6 (July- 

August 1972), pp. 1133-1145. 

3. Graham, R. L., and Pollak, H. O., "On the Addressing Problem for Loop Switch- 

ing," B.S.T.J., 50, No. 8 (October 1971), pp. 2495-2519.